COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002			Solutions to CS206 Final Exam 
C00005 00003	2. To find all the substructures of an s-expression, car and cdr recursion is
C00008 00004	3. Partition can be done in a number of ways that generate multiple copies of
C00010 00005	4. There are many ways to prove our theorem about length, so I include here just
C00013 00006	5. The trick to avoiding unnecessary parentheses is to remember whether you
C00015 00007	6. The best way to figure this out, of course, is to run lcom4. I did this
C00016 ENDMK
C⊗;
		Solutions to CS206 Final Exam 

1.  There are many ways to solve this problem.  Since somewhat different actions
are called for in the case of an even-length list than an odd one, my first
solution uses two seperate functions based on this test.

(DEFUN ALT1 (U) 
       (COND ((EVENP (LENGTH U)) (ALTEVEN U)) (T (ALTODD U)))) 

(DEFUN EVENP (N) (EQ (REMAINDER N 2.) 0.)) 

(DEFUN ALTEVEN (U) 
       (COND ((NULL (CDR U)) NIL)
	     (T (CONS (CADR U) (ALTEVEN (CDDR U)))))) 

(DEFUN ALTODD (U) 
       (COND ((NULL U) NIL) (T (CONS (CAR U) (ALTODD (CDDR U)))))) 

Another way to solve the problem is to simultaneously build the solution for the
even case and for the odd one, and then return the appropriate one when it
becomes obvious which case is being dealt with.  I use reverse to avoid many
unnecessary appends.

(DEFUN ALTONE (U) (ALTTWO U NIL NIL)) 

(DEFUN ALTTWO (U ODD EVEN) 
       (COND ((NULL U) (REVERSE EVEN))
	     ((NULL (CDR U)) (REVERSE (CONS (CAR U) ODD)))
	     (T (ALTTWO (CDDR U)
			(CONS (CAR U) ODD)
			(CONS (CADR U) EVEN))))) 

Finally, those of you who remember the story of the mathematician and the tea
kettle will probably appreciate this solution based on the case that has already
been solved, namely the example of the alt function shown in class that always
includes the first element.

(DEFUN ALTWUN (U) (REVERSE (ALT (REVERSE U)))) 

(DEFUN ALT (U) 
       (COND ((OR (NULL U) (NULL (CDR U))) U)
	     (T (CONS (CAR U) (ALT (CDDR U)))))) 

2. To find all the substructures of an s-expression, car and cdr recursion is
necessary.  One solution to this problem is based on writing two functions
which search through the s-expr, one breaking down the car of the sexpr and the
other breaking down the cdr. These two functions thus provide a test of every
subexpression against every other (including comparison to itself, sadly).

(DEFUN ISCOMPACT (U) 
       (COND ((ATOM U) T)
	     (T (AND (ISCOMPACT1 (CAR U) U )
		     (ISCOMPACT1 (CDR U) U )))))

(DEFUN ISCOMPACT1 (A D) 
       (COND ((ATOM A) T)
	     (T (AND (SAMETEST A D)
		     (ISCOMPACT1 (CAR A) D)
		     (ISCOMPACT1 (CDR A) D))))) 

(DEFUN SAMETEST (A D) 
       (COND ((ATOM D) T)
	     ((EQUAL A D) (EQ A D))
	     (T (AND (SAMETEST A (CAR D)) (SAMETEST A (CDR D)))))) 

A different sort of solution consists of keeping a list of subexpressions that
have already been found.  Whenever the expression under consideration is equal
to one of these (member does this test nicely), it is tested for whether it is
eq.  The funny use of the car of the member is based on member actually
returning the list with the matching element at the head of it whenever one is
found.

(DEFUN ISCOMPACT2 (U) (ISCMPT U NIL)) 

(DEFUN ISCMPT (NEW FOUND) 
       (COND ((ATOM NEW) T)
	     (T ((LAMBDA (Z) 
			 (COND (Z (AND (EQ NEW (CAR Z))
				       (ISCMPT (CAR NEW) FOUND)
				       (ISCMPT (CDR NEW) FOUND)))
			       (T (AND (ISCMPT (CAR NEW)
					       (CONS (CDR NEW) FOUND))
				       (ISCMPT (CDR NEW)
					       (CONS (CAR NEW)
						     FOUND))))))
		 (MEMBER NEW FOUND))))) 
3. Partition can be done in a number of ways that generate multiple copies of
the same number lists. To do it without having to generate and then remove all
those duplicates, a test on whether the mid-point of generation has been reached
is needed.

(DEFUN PARTITION (N) (PARTN N 1)) 

(DEFUN PARTN (BIG LITTLE) 
       (COND ((EQ BIG LITTLE) (LIST (LIST LITTLE)))
	     ((NOT (LESSP BIG (* 2 LITTLE)))
	       (APPEND (PARTN BIG (+ LITTLE 1))
		       (SPLICE LITTLE (PARTN (- BIG LITTLE) LITTLE))))
	     (T (PARTN BIG (+ LITTLE 1))))) 

(DEFUN SPLICE (HEAD LIST) 
       (MAPCAR (FUNCTION (LAMBDA (ELEMENT) (CONS HEAD ELEMENT)))
	       LIST)) 

A somewhat different approach builds the smaller partitions and uses only the parts
of them that are needed with each larger addend.


(DEFUN PARTISHUNS (N) (CONS (LIST N) (PART N 1.))) 

(DEFUN PART (N M) 
       (COND ((EQ N M) NIL)
	     (T (APPEND (PART1 (PARTISHUNS M) (- N M))
			(PART N (+ 1. M)))))) 

(DEFUN PART1 (U X) 
       (COND ((NULL U) NIL)
	     ((CHK X (CAR U))
	      (CONS (CONS X (CAR U)) (PART1 (CDR U) X)))
	     (T (PART1 (CDR U) X)))) 

(DEFUN CHK (X U) 
       (COND ((NULL U) T)
	     ((NOT (GREATERP (CAR U) X)) (CHK X (CDR U)))
	     (T NIL))) 
4. There are many ways to prove our theorem about length, so I include here just
a sketch of one way to do it. 

We wish to show that 

∀v P(u) = [ length[u*v] = length u + length v ]

Since u and v are lists, the notion of using the list induction schema naturally
arises. Our schema is as follows.

{ P(nil) ∧ ∀u:[ u≠nil ∧[P(du)→P(u)]] } → ∀u: P(u)

For the null case we have a simple substitution.

∀v:u=nil ∧[ length[u*v] =?= length u + length v ]

length[v] =?= length u + length v		sub definition of append nil

length[v] =?= [if null u then 0] + length v	sub definition of length [nil]

length v = 0 + length v				definition of plus

With the null case proven, we can now prove P(u) follows from P(du) when u≠nil.

length[u*v] = length[au.[du*v]]			definition of append for u≠nil

	    = if n[au.[du*v]]then 0 else 1 + length[du*v]	def of length

	    = 1 + length[du*v]			atom[nil] ∧ ∀xy: ¬atom[x.y]

	    = 1 + [length[du] + length v]	induction hypothesis

	    = [1 + length[du]] + length v	assoc rule for addition

	    = length u + length v		apply def of length backwards

Since we have shown that P(u) follows from P(du) and that P(nil) is true, we
have proven P(u) for all u.

No proof of termination was required for the exam. 
5. The trick to avoiding unnecessary parentheses is to remember whether you
are inside a plus or a times when converting. Flag carries this information;
inside a plus no additional parentheses are needed. Since the same is true at
the top level, we start the flag at plus.

(DEFUN POLYPRINT (E) (PP E 'PLUS))
 
(DEFUN PP (E FLAG) 
       (COND ((ATOM E) (LIST E))
	     ((EQ (CAR E) 'TIMES)
	      (PPEACH (CDR E) 'TIMES))
	     ((EQ (CAR E) 'PLUS)
	      (COND ((EQ FLAG 'PLUS) (PLUSEACH (CDR E) FLAG))
		    (T (APPEND (LIST 'LP)
			       (PLUSEACH (CDR E) FLAG)
			       (LIST 'RP)))))))
 
(DEFUN PPEACH (E F) 
       (COND ((NULL E) NIL)
	     (T (APPEND (PP (CAR E) F) (PPEACH (CDR E) F)))))
 
(DEFUN PLUSEACH (E F) 
       (COND ((NULL E) NIL)
	     ((NULL (CDR E)) (PP (CAR E) F))
	     (T (APPEND (PP (CAR E) F)
			'(PLUS)
			(PLUSEACH (CDR E) F)))))
6. The best way to figure this out, of course, is to run lcom4. I did this
at LOTS and here's what it said. Since the format of constants is different
from the class notes, I'll accept most anything.

(DEFUN FF (X) (COND ((ATOM X) X) (T (FF (CAR X))))) 

(LAP FF SUBR) 
(PUSH P 1) 
(MOVE 1 0 P) 
(CALL 1 (QUOTE ATOM)) 
(JUMPE 1 G0003) 
(MOVE 1 0 P) 
(JRST 0 G0002) 
G0003 
(HLRZ@ 1 0 P) 
(CALL 1 (QUOTE FF)) 
G0002 
(SUB P (% 0 0 1 1)) 
(POPJ P) 
NIL